#include <string>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        //预处理，判断 i-j 字符串是否回文
        bool isPlim[len][len];
        for(int i = 0; i < len; i++)
            for(int j = 0; j < len; j++)
                isPlim[i][j] = false;
        int dp[len];
        for(int i = 0; i < len; i++){
            for(int j = 0; j <= i; j++){
                char c1 = s[i];
                char c2 = s[j];
                if(c1 == c2 && (j + 1 >= i || isPlim[j + 1][i - 1])){
                    isPlim[j][i] = true;
                }
            }
        }
        //动规
        for(int i = 0; i < len; i++){
            if(isPlim[0][i]){
                dp[i] = 0;
            }else{
                dp[i] = i;
                for(int j = 1; j <= i; j++){
                    if(isPlim[j][i]){
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }

        return dp[len - 1];
    }
};